package lb.test.core.alg;

import java.util.Arrays;

public class MyAlg {

    public static void testAlg() {
        int[] arr = {6,43,23,6,76,73,21,5,76,85,343,0,7,8,12,666,3,1};
        int[] result = {0, 1, 3, 5, 6, 6, 7, 8, 12, 21, 23, 43, 73, 76, 76, 85, 343, 666};

        new SelectorSort().doSortAndPrintResult(arr, result);
        new InsertSort().doSortAndPrintResult(arr, result);
        new BubbleSort().doSortAndPrintResult(arr, result);
        new BubbleSortOpt().doSortAndPrintResult(arr, result);
        new ShellSort().doSortAndPrintResult(arr, result);
        new MergeSort().doSortAndPrintResult(arr, result);
        new MergeSortNoRec().doSortAndPrintResult(arr, result);
        new QuickSort().doSortAndPrintResult(arr, result);
        new CountingSort().doSortAndPrintResult(arr, result);
        new HeapSort().doSortAndPrintResult(arr, result);

        for (int i : result) {
            System.out.println("BinarySearch v="+i+",idx="+doBinarySearch(result, i, 0, result.length - 1));
        }
    }

    private static int doBinarySearch(int[] arr, int value, int start, int end) {
        if (start > end) {
            return -1;
        }
        int mid = (end + start) / 2;
        if (arr[mid] > value) {
            return doBinarySearch(arr, value, start, mid - 1);
        } else if (arr[mid] < value) {
            return doBinarySearch(arr, value, mid + 1, end);
        } else {
            return mid;
        }
    }


    private static class SelectorSort extends BaseSortAlgorithm {
        @Override
        public void doSort(int[] arr) {

            for (int i = 0; i < arr.length; i++) {
                int minValueIdx = i;
                for (int j = i + 1; j < arr.length; j++) {
                    if (arr[minValueIdx] > arr[j]) {
                        minValueIdx = j;
                    }
                }
                if (minValueIdx != i) {
                    swap(arr, i, minValueIdx);
                }
            }
        }
    }

    private static class InsertSort extends BaseSortAlgorithm {

        @Override
        public void doSort(int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                int tagValueIdx = 0;
                for (int j = i - 1; j >= 0; j--) {
                    if (arr[j] <= arr[i]) {
                        tagValueIdx = j + 1;
                        break;
                    }
                }
                if (tagValueIdx != i) {
                    insert(arr, tagValueIdx, i, arr[i], true);
                }
            }
        }
    }

    private static class BubbleSort extends BaseSortAlgorithm {

        @Override
        public void doSort(int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr.length - 1; j++) {
                    if (arr[j] > arr[j + 1]) {
                        swap(arr, j, j + 1);
                    }
                }
            }
        }
    }

    //冒泡优化版本
    private static class BubbleSortOpt extends BaseSortAlgorithm {

        @Override
        public void doSort(int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                boolean isDest = true;
                for (int j = 0; j < arr.length - 1; j++) {
                    if (arr[j] > arr[j + 1]) {
                        isDest = false;
                        swap(arr, j, j + 1);
                    }
                }
                if (isDest) {
                    break;
                }
            }
        }
    }

    //希尔排序
    private static class ShellSort extends BaseSortAlgorithm {

        @Override
        public void doSort(int[] arr) {
            for (int inc = arr.length / 2; inc > 0; inc /= 2) {
                for (int i = inc; i < arr.length; i++) {
                    doBuckInsertSort(arr, inc, i);
                }
            }
        }

        private void doBuckInsertSort(int[] arr, int inc, int i) {
            int temp = arr[i];
            int j;
            for (j = i - inc; j >= 0 && temp < arr[j]; j -= inc) {
                arr[j + inc] = arr[j];
            }
            arr[j + inc] = temp;
        }
    }

    private static class MergeSort extends BaseSortAlgorithm {

        @Override
        public void doSort(int[] arr) {
            doMergeSort(arr, 0, arr.length - 1);
        }

        private void doMergeSort(int[] arr, int start, int end) {
            if (start < end) {
                int mid = (start + end) / 2;
                doMergeSort(arr, start, mid);
                doMergeSort(arr, mid + 1, end);
                doMergeArr(arr, start, mid, end);
            }
        }

        protected void doMergeArr(int[] arr, int start, int mid, int end) {
            int[] a = new int[end - start + 1];
            int i = start, j = mid + 1, k = 0;
            while (i <= mid && j <= end) {
                if (arr[i] < arr[j]) {
                    a[k++] = arr[i++];
                } else {
                    a[k++] = arr[j++];
                }
            }
            while(i <= mid) a[k++] = arr[i++];
            while(j <= end) a[k++] = arr[j++];
            for (i = 0; i < k; i++) {
                arr[start++] = a[i];
            }
        }
    }

    //非递归实现的归并排序
    private static class MergeSortNoRec extends MergeSort {
        @Override
        public void doSort(int[] arr) {
            for (int i = 1; i < arr.length; i += i) {
                int start = 0;
                int mid = start + i - 1;
                int end = mid + i;

                while (end < arr.length) {
                    doMergeArr(arr, start, mid, end);
                    start = end + 1;
                    mid = start + i - 1;
                    end = mid + i;
                }

                if (start < arr.length && mid < arr.length) {
                    doMergeArr(arr, start, mid, arr.length - 1);
                }
            }
        }
    }

    private static class QuickSort extends BaseSortAlgorithm {

        @Override
        public void doSort(int[] arr) {
            doQuickSort(arr, 0, arr.length - 1);
        }

        private void doQuickSort(int[] arr, int start, int end) {
            int tagIdx = start;
            int ts = start + 1;
            for (int i = ts; i <= end; i++) {
                if (arr[i] < arr[tagIdx]) {
                    insert(arr, tagIdx, i, arr[i], true);
                    tagIdx++;
                }
            }
            if (tagIdx - start > 1) {
                doQuickSort(arr, start, tagIdx - 1);
            }
            if (end - tagIdx > 1) {
                doQuickSort(arr, tagIdx + 1, end);
            }
        }
    }
    private static class HeapSort extends BaseSortAlgorithm {

        @Override
        public void doSort(int[] arr) {
            heapSort(arr, arr.length);
        }

        /**
         *  根元素下沉操作，执行删除操作相当于把最后
         *  一个元素赋给根元素之后，然后对根元素执行下沉操作
         *
         * @param arr
         * @param parent 要下沉元素的下标
         * @param length 数组长度
         */
        private void downAdjust(int[] arr, int parent, int length) {
            int temp = arr[parent];
            int child = 2 * parent + 1;

            while (child < length) {
                if (child + 1 < length && arr[child] <= arr[child + 1]) {
                    child++;
                }
                if (temp > arr[child]) {
                    break;
                }
                arr[parent] = arr[child];
                parent = child;
                child = 2 * parent + 1;
            }
            arr[parent] = temp;
        }

        private void heapSort(int[] arr, int length) {
            for (int i = (length - 2) / 2; i >= 0; i--) {
                downAdjust(arr, i, length);
            }

            for (int i = length - 1; i >= 1; i--) {
                swap(arr, 0, i);
                downAdjust(arr, 0, i);
            }
        }
    }

    //对数字排序可用，其他数字型排序：桶排序、基数排序
    private static class CountingSort extends BaseSortAlgorithm {

        @Override
        public void doSort(int[] arr) {
            if(arr == null || arr.length < 2) {
                return;
            }

            int n = arr.length;
            int max = arr[0];
            int min = arr[0];
            for (int i = 1; i < n; i++) {
                if(max < arr[i]) {
                    max = arr[i];
                }
                if (min > arr[i]) {
                    min = arr[i];
                }
            }
            int[] temp = new int[max - min + 1];
            for (int i = 0; i < n; i++) {
                temp[arr[i] - min]++;
            }
            int k = 0;
            for (int i = 0; i < temp.length; i++) {
                for (int j = temp[i]; j > 0; j--) {
                    arr[k++] = i + min;
                }
            }
        }
    }

    private static abstract class BaseSortAlgorithm implements SortAlgorithm {

        public String getAlgorithmName() {
            return getClass().getSimpleName();
        }

        public void doSortAndPrintResult(int[] tagArr, int[] resArr) {
            int[] arr = null;

            arr = Arrays.copyOf(tagArr, tagArr.length);
            doSort(arr);

            String printer = String.format("%1$-20s testResult=%2$b, %3$s", getAlgorithmName() + ":", Arrays.equals(arr, resArr), Arrays.toString(arr));
            System.out.println(printer);
        }

        protected void swap(int[] arr, int idx1, int idx2) {
            int temp = arr[idx1];
            arr[idx1] = arr[idx2];
            arr[idx2] = temp;
        }

        /**
         * 插入到数组中，导致移动元素过多，性能下降
         * @param start 起始元素位置
         * @param end 结束元素位置
         * @param value 待插入的值
         * @param insertToHead true插入头部 所有节点向后移动，最后一个元素丢弃
         */
        protected void insert(int[] arr, int start, int end, int value, boolean insertToHead) {
            if (insertToHead) {
                for (int i = end; i > start; i--) {
                    arr[i] = arr[i - 1];
                }
                arr[start] = value;
            } else {
                for (int i = start; i < end; i++) {
                    arr[i] = arr[i + 1];
                }
                arr[end] = value;
            }
        }
    }

    private interface SortAlgorithm {
        void doSort(int[] arr);
    }

}
